package q953_isAlienSorted;

import java.util.HashMap;
import java.util.Map;

public class Solution_1 {
    /*
    此题的关键在于两个词语之间的字典序判断
    假设具有 A B C 三个单词
    如果 A < B 且 B < C 则必然是 A < C 所以只需要两两比较即可
     */
    public boolean isAlienSorted(String[] words, String order) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < order.length(); i++) {
            map.put(order.charAt(i), i);
        }

        for (int i = 1; i < words.length; i++) {
            if (!compareTwoWords(words[i - 1], words[i], map)) {
                return false;
            }
        }
        return true;
    }

    /*
    字典序的判断在于
    先判断首个字符是否满足word1[0] < word2[0]如果满足则直接返回true
    如果是相等 则后移指针 如果为大于则可直接返回false
    而指针比较结束后 考虑指针的位置和两个单词的长度即可
     */
    public boolean compareTwoWords(String word1, String word2, Map<Character, Integer> map) {
        int len = 0;
        while (len < word1.length() && len < word2.length()) {
            if (map.get(word1.charAt(len)) < map.get(word2.charAt(len))) {
                return true;
            } else if (map.get(word1.charAt(len)) == map.get(word2.charAt(len))) {
                len++;
            }else {
                return false;
            }

        }

        return len == word1.length() && len <= word2.length();
    }
}
